package bin_tree.bst;

import java.util.NoSuchElementException;

/**
 * 基于int的二分搜索树
 */
public class MyBST {
    // 树根节点
    private TreeNode root;
    // 当前有效节点的个数
    private int size;
    // 节点类定义
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void remove(int val) {
        remove(root,val);
    }

    /**
     * 在当前以root为根的BST中删除值为val的节点，返回删除后的树根节点
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        // base case
        if (root == null) {
            // 此时没有值为val的节点
            return null;
        }else if (val < root.val) {
            // 在左子树中的删除操作
            root.left = remove(root.left,val);
            return root;
        }else if (val > root.val) {
            // 在右子树中的删除
            root.right = remove(root.right,val);
            return root;
        }else {
            // 此时root就是待删除的节点
            if (root.left == null) {
                // 类似于删除最小值
                TreeNode right = root.right;
                root.right = root = null;
                size --;
                return right;
            }else if (root.right == null) {
                // 类似于删除最大值，返回左树树根
                TreeNode left = root.left;
                root.left = root = null;
                size --;
                return left;
            }
            // 此时左右子树都不为空，找到后继节点
            // 右子树最小值
            TreeNode successor = findMinNode(root.right);
            // 移除右子树的最小值时，已经维护了size属性~
            successor.right = removeMin(root.right);
            successor.left = root.left;
            root.left = root.right = root = null;
            return successor;
        }
    }

    public int removeMin() {
        TreeNode minNode = findMinNode(root);
        root = removeMin(root);
        return minNode.val;
    }

    private TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            TreeNode right = root.right;
            root.left = root = null;
            size --;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public int removeMax() {
        TreeNode maxNode = findMaxNode(root);
        root = removeMax(root);
        return maxNode.val;
    }
    // 在当前以root为根的BST中，删除最大值节点，返回删除后的树根节点
    private TreeNode removeMax(TreeNode root) {
        if (root.right == null) {
            // 此时root就是最大值节点
            TreeNode left = root.left;
            root.left = root = null;
            size --;
            return left;
        }
        // 此时继续在右子树中删除节点
        root.right = removeMax(root.right);
        return root;
    }

    public int max() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!Do not has max node");
        }
        TreeNode maxNode = findMaxNode(root);
        return maxNode.val;
    }
    // 在以root为根的BST中返回最大值节点
    private TreeNode findMaxNode(TreeNode root) {
        // base case
        if (root.right == null) {
            // root就是要查找的最大值节点
            return root;
        }
        // 继续在右子树中查找
        return findMaxNode(root.right);
    }

    public int min() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!Do not has min node");
        }
        TreeNode minNode = findMinNode(root);
        return minNode.val;
    }

    private TreeNode findMinNode(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        return findMinNode(root.left);
    }

    public boolean contains(int val) {
        return contains(root,val);
    }

    private boolean contains(TreeNode root, int val) {
        // base case
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }else if (val < root.val) {
            // 左子树中继续查找
            return contains(root.left,val);
        }
        return contains(root.right,val);
    }


    public void add(int val) {
        root = add(root,val);
    }

    /**
     * 在当前以root为根的二分搜索树中插入一个新的值val，并返回插入后新的树根节点
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val) {
        // base case
        if (root == null) {
            TreeNode node = new TreeNode(val);
            size ++;
            return node;
        }else if (val < root.val) {
            // 在左子树中的插入
            root.left = add(root.left,val);
            return root;
        }
        root.right = add(root.right,val);
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 在当前以root为根的BST中，将当前节点的层次和值，拼接到sb对象中
     * @param root
     * @param depth
     * @param sb
     */
    private void generateBSTString(TreeNode root, int depth, StringBuilder sb) {
        // base case
        if (root == null) {
            sb.append(generateDepthString(depth)).append("NULL\n");
            return;
        }
        sb.append(generateDepthString(depth)).append(root.val).append("\n");
        // 继续处理左子树
        generateBSTString(root.left,depth + 1,sb);
        // 继续处理右子树
        generateBSTString(root.right,depth + 1,sb);
    }
    // 打印当前节点的深度
    // depth每+1一次 多加一个"--"
    private String generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}
